package AVLTree;

import java.util.LinkedList;
import java.util.List;

//只实现Integer的AVLTree
public class AVLTree {
    Node root;
    List<Integer> ans=new LinkedList<>();

    private int height(Node k)
    {
        if(k!=null)
        {
            return k.height;
        }
        return 0;
    }

    //LL 右旋 旋转返回 最新的根结点 参数是左右高度差为2的那个结点
    private Node leftLeftRotation(Node k)
    {
        Node temp=k.left;
        k.left=temp.right;
        temp.right=k;
        //因为是高度 所以只有旋转的那两个变化
        k.height=Math.max(height(k.left),height(k.right))+1;
        temp.height=Math.max(height(temp.left),height(temp.right))+1;
        return temp;
    }

    //RR 左旋 返回最新的根结点  参数是左右高度差为2的那个结点
    private Node rightRightRotation(Node k)
    {
        Node temp=k.right;
        k.right=temp.left;
        temp.left=k;
        //因为是高度 所以只有旋转的那两个变化
        k.height=Math.max(height(k.left),height(k.right))+1;
        temp.height=Math.max(height(temp.left),height(temp.right))+1;
        return temp;
    }

    //LR 先左旋 再右旋 参数是左右高度差为2的那个结点(高度变化已经蕴含其中)
    private Node leftRightRotation(Node k)
    {
        k.left=rightRightRotation(k.left);
        return leftLeftRotation(k);
    }

    //RL 先右旋 在左旋 参数是左右高度差为2的那个结点(高度变化已经蕴含其中)
    private Node rightLeftRotation(Node k)
    {
        k.right=leftLeftRotation(k.right);
        return rightRightRotation(k);
    }

    private Node insert(Node root,int k)
    {
        if(root==null)
        {
            root=new Node(k);
            if(this.root==null)
                this.root=root;
        }
        else
        {
            if(k<root.value)
            {
                root.left=insert(root.left,k);
                if(height(root.left)-height(root.right)>1)
                {
                    //LR
                    if(k>root.left.value)
                        return leftRightRotation(root);
                    //LL
                    else
                        return leftLeftRotation(root);
                }
            }
            else if(k>root.value)
            {
                root.right=insert(root.right,k);
                if(height(root.right)-height(root.left)>1)
                {
                    //RL
                    if(k<root.right.value)
                        return rightLeftRotation(root);
                    //RR
                    else
                        return rightRightRotation(root);
                }
            }
            else
            {
                System.out.println("不允许插入重复元素");
            }
        }
        root.height=Math.max(height(root.left),height(root.right))+1;
        return root;
    }

    public Node insert(int k)
    {
        this.root=insert(root,k);
        return this.root;
    }

    private Node delete(Node root,int k)
    {
        if(root==null)
            return null;
        if(k<root.value)
        {
            root.left=delete(root.left,k);
        }
        else if(k>root.value)
        {
            root.right=delete(root.right,k);
        }
        else if(k==root.value)
        {
            //如果右子树 以及左子树 都存在 则 找到右子树最小的点 然后这点连接原左子树 和右子树删除该点后的点
            if(root.left!=null&&root.right!=null)
            {
                int min=findMin(root.right);
                Node temp=new Node(min);
                temp.right=delete(root.right,min);
                temp.left=root.left;
                root=temp;
            }
            else
            root=root.left==null?root.right:root.left;
        }
        if(root==null)
            return null;

        if(height(root.left)-height(root.right)>1)
        {
         if(height(root.left.left)>=height(root.left.right))
             return leftLeftRotation(root);
         else
             return leftRightRotation(root);

        }
        else if(height(root.right)-height(root.left)>1)
        {
            if(height(root.right.right)>=height(root.right.left))
                return rightRightRotation(root);
            else
                return rightLeftRotation(root);
        }
        root.height=Math.max(height(root.left),height(root.right));
        return root;
    }

    private int findMin(Node root)
    {
        while(root.left!=null)
        {
            root=root.left;
        }
        return root.value;
    }

    public void delete(int k)
    {
        this.root=delete(root,k);
    }

    private void show(Node root)
    {
        if(root==null)
            return;
        show(root.left);
        ans.add(root.value);
        show(root.right);
    }

    public List<Integer> show()
    {
        ans.clear();
        show(root);
        return ans;
    }

    private class Node
    {
        int value;
        int height=0;
        Node right=null;
        Node left=null;

        public Node(int value)
        {
            this.value=value;
        }
    }
}
